package 分治.快排;

import com.sun.org.apache.bcel.internal.generic.SWAP;
// 1.c>= k  去[right,r]找第 k 大，
// 2. b+c >=k 返回 key
// 1，2不成立，去[l，left] 找第 k-b-c大
import java.util.Random;

// 快速选择算法
public class 数组中第K个最大元素215 {


    public int findKthLargets(int []nums,int k){
       return  qsort(nums,0,nums.length-1,k);


    }
    public int qsort(int [] nums,int l,int r,int k){

        // l>r
        if(l==r) return nums[l];

        int index = nums[new Random().nextInt(r-l+1)+l];
        int right = r+1,left = l-1, i = l;
        while(i<right)
        {
            if(nums[i]<index) swap(nums,++left,i++);
            else if (nums[i] > index) swap(nums,--right,i);
            else i++;
        }

        // 分类讨论
        // [l,left],[left+1,right-1] ,[right,r]
        int b = right-1-left,c = r-right+1;
        if(c>=k) return qsort(nums,right,r,k);
        else if (b+c>=k) return index;
        else return qsort(nums,l,left,k-b-c);



    }
    public void swap(int [] nums,int j,int k)
    {
        int temp = nums[j];
        nums[j] = nums[k];
        nums[k] = temp;
    }
}
